// BestBinarySearchTree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#define MAX 65536
#define MAXNUM 10

void bestBinSearchTree(int n, float p[], float q[], float w[][MAXNUM], float m[][MAXNUM], int root[][MAXNUM])
{
	int i = 0, j = 0, k = 0, r = 0;
	float t;

	for(i=0;i<n;i++)
	{
		w[i+1][i] = q[i];
		m[i+1][i] = q[i];
	}

	for(k=0;k<n;k++)
	{
		for(i=1;i<=n-k;i++)
		{
			j = i + k;
			w[i][j] = w[i][j-1] + p[i] + q[i];
			m[i][j] = m[i+1][j];
			root[i][j] = i;

			for(r=i+1;r<=j;r++)
			{
				t = m[i][r-1] + m[r+1][j];
				if(t<m[i][j])
				{
					m[i][j] = t;
					root[i][j] = r;
				}

				m[i][j] += w[i][j];

			}

		}
	}
}

int _tmain(int argc, _TCHAR* argv[])
{

	float m[MAXNUM][MAXNUM]=;
	float w[MAXNUM][MAXNUM]=;
	int root[MAXNUM][MAXNUM]=;

	float p[MAXNUM] = {0.00,0.15,0.10,0.05,0.10,0.20};  
	float q[MAXNUM] = {0.05,0.10,0.05,0.05,0.05,0.10};  

	bestBinSearchTree(6, p, q, m, w, root);

	for(int i=0;i<6;i++)
		for(int j=0;j<6;j++)
			printf("%0.2f  ",m[i][j]);

	getchar();
	return 0;
}

